
def ways(max_step, height):
    # 基本情况：不随 max_step 的变化而变化的过程
    if height == 0 or height == 1:
        return 1

    # 爬到 height 层的方法数
    steps = 0

    for i in range(1, min(max_step, height) + 1):
        steps += ways(max_step, height - i) # height >= max_step

    return steps

# print(ways(2, 5)) # max_step < height
print(ways(5, 2)) # max_step > height

# 爬到 height 层的方法
# ways(height - 1) + ways(height - 2) + ... + ways(height - max_step)
#
# max_step = 2
# 2 -> (2 - 1) + (2 - 2)
# 3 -> (3 - 1) + (3 - 2)